package Algorithm;

public class LC74 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length;
        int n=matrix[0].length;
        int l=0;
        int r=m*n-1;
        while(l<=r){
            int mid=(r-l)/2+l;
            int x=matrix[mid/n][mid%n];
            if(x<target){
                l=mid+1;
            }else if(x > target){
                r=mid-1;
            }else{
                return true;
            }
        }
        return false;
    }


//    public boolean searchMatrix(int[][] matrix, int target) {
//        int m=matrix.length;
//        int n=matrix[0].length;
//        if(m==1 && n==1) return target==matrix[0][0]?true:false;
//        for(int i=0;i<m;i++){
//            if(matrix[i][n-1]<target){
//                continue;
//            }else if(matrix[i][n-1]>target){
//                int l=0;
//                int r=n-1;
//                while(l<r){
//                    int mid=(l+r)/2;
//                    if(matrix[i][mid]>target){
//                        r=mid;
//                    }else if(matrix[i][mid]<target){
//                        l=mid+1;
//                    }else{
//                        return true;
//                    }
//                }
//            }else{
//                return true;
//            }
//        }
//        return false;
//    }
}
